package com.javatest2;

import java.util.Arrays;

/**
 * @author LL
 * 希尔排序，插入排序基础上改进
 * @create 2021-01-20 11:36
 */
public class Subject8 {

    public static void test(final int[] a) {
        final int n = a.length;
        int h = 1;
        while (h < n / 3) {
            h = h * 3 + 1;//增量序列为: 1,4,13,40,121,364,···
        }
        while (h >= 1) {//外层循环将h按照增量序列递减
            for (int i = h; i < n; i++) {
                int j;
                final int temp = a[i];
                //从待排序元素往前遍历比较，减量为h
                for (j = i; j >= h && temp < a[j - h]; j -= h) {
                    a[j] = a[j - h];
                }
                a[j] = temp;
            }
            h /= 3;
        }
        System.out.println(Arrays.toString(a));
    }

    public static void main(final String[] args) {
        final int[] a = {37, 60, 74, 15, 25, 23, 0, 9, 6, 8, 5, 2, 3};
        /*for (int i = 0; i < a.length; i++) {
            a[i] = (int) (Math.random() * 10 + 1);
        }*/
        test(a);
    }


}
